#include<vector>
using namespace std;

class Solution {
    public:
        void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
            int n = A.size();
            dfs(A,B,C,n);
        }
        void dfs(vector<int>& X, vector<int>& Y, vector<int>& Z,int n){
            //exit
            if(n == 1){
                Z.push_back(X.back());
                X.pop_back();
                return;
            }
            dfs(X,Z,Y,n-1);
            Z.push_back(X.back());
            X.pop_back();
            dfs(Y,X,Z,n-1);
        }
    };

    //dfs任务：将A上的盘子n个盘子借助B放在C上
    //子问题：将A上的n-1个盘子借助C放在B上，再讲A上的back盘子放在C上，再将B上的n-1个盘子借助A放在C上
    //函数出口，当n==1时